#include <cstdio>
#include <cstring>
#include <list>
#include <iostream>
#include <fstream>
#include "graph.h"
#include "graphalgorithm.h"
#include <map>

#define INPUT_BUFFER_SIZE 1<<13

int main(int argc, char *argv[]) {
  if (argc < 2) {
    std::cerr << "Usage: " << argv[0] << " inputFile" << std::endl;
    return 1;
  }

  std::string fileName(argv[1]);
  std::ifstream fin;
  fin.open(fileName.c_str());
  if(!fin) { // file couldn't be opened
    std::cerr << "Error: file could not be opened" << std::endl;
    return 1;
  }

  std::list<int> seq; // input sequence
  std::map<int, Node*> lut;  // hash table to quickly locate the Node
  auto seqIt = seq.begin();

  int nodeId, delimId = FIRST_NODE;
  char *inputLine = (char *)malloc(INPUT_BUFFER_SIZE);
  Node *prevNode = NULL, *node;


  while (!fin.eof()) {
    fin.getline(inputLine, INPUT_BUFFER_SIZE);
    if (inputLine[0] == ';') // comment line
      continue;

    char *nextToken = strtok(inputLine, " ");
    if (nextToken) { // insert delim node at the beginning of each sequence (input line)
      seq.push_back(delimId);
      node = new Node(delimId, ++seqIt);
      lut[delimId] = node;
      if (delimId != FIRST_NODE) {
        prevNode->addNext(node);
      }
      prevNode = node;
      delimId--;
    }
    while (nextToken) {
      nodeId = atoi(nextToken);
      nextToken = strtok(NULL, " ");

      seq.push_back(nodeId);

      // node not found
      // create entry for node in lookup table
      if (lut.find(nodeId) == lut.end()) {
        node = new Node(nodeId, ++seqIt);
        lut[nodeId] = node;
      }
      else {
        node = lut[nodeId];
        node->addPos(++seqIt);
      }

      prevNode->addNext(node);
      prevNode = node;

    }
  }

  seq.push_back(LAST_NODE);
  node = new Node(LAST_NODE, ++seqIt);
  lut[LAST_NODE] = node;
  prevNode->addNext(node);
  prevNode = node;

  fin.close();

  GraphAlgorithm algo;
  algo.setGraph(lut);
  algo.setSequence(seq);



#ifdef VERBOSE
  for (std::map<int, Node*>::iterator lutIt = lut.begin();
       lutIt != lut.end();
       lutIt++) {
    std::cout << *(lutIt->second);
    std::cout << "Pos: ";
    for (auto it2 = lutIt->second->pos.begin(); it2 != lutIt->second->pos.end(); ++it2) {
      std::cout << **it2 << " ";
    }
    std::cout << "\n";
  }
  std::cout << "Hello\n";
  auto foo = seq.begin();
  while (++foo != seq.end()) {
    std::cout << *foo << std::endl;
  }

#endif

  int maxGirth = 20;
  bool changed = false;
  int ret;
  for (int i = 3; i <= maxGirth; i++) {
    DPRINTF(("--------------------Find cycle with maxGirth = %d\n", i));
    std::list<int>::iterator it;
    std::queue<std::list<int>::iterator> queue;
    node = lut[FIRST_NODE]->nexts.begin()->second->toNode;
    for (auto it = node->pos.begin(); it != node->pos.end(); ++it) {
      queue.push(*it);
    }

    while (!queue.empty()) {
      it = queue.front();
      queue.pop();
      ret = algo.findOneComponentCycle(it, i);
      if (ret != NO_CYCLE_FOUND) {
        while (!queue.empty()) {
          queue.pop();
        }
        node = lut[FIRST_NODE]->nexts.begin()->second->toNode;
        for (auto it = node->pos.begin(); it != node->pos.end(); ++it) {
          queue.push(*it);
        }
#ifdef VERBOSE
        for (std::map<int, Node*>::iterator lutIt = lut.begin();
             lutIt != lut.end();
             lutIt++) {
          std::cout << *(lutIt->second);
        }
        std::cout << seq;
#endif
        continue;
      }
      ret = algo.findTwoComponentCycle(it, i);
      if (ret != NO_CYCLE_FOUND) {
        while (!queue.empty()) {
          queue.pop();
        }
        node = lut[FIRST_NODE]->nexts.begin()->second->toNode;
        for (auto it = node->pos.begin(); it != node->pos.end(); ++it) {
          queue.push(*it);
        }
#ifdef VERBOSE
        for (std::map<int, Node*>::iterator lutIt = lut.begin();
             lutIt != lut.end();
             lutIt++) {
          std::cout << *(lutIt->second);
          std::cout << "Pos: ";
          for (auto it2 = lutIt->second->pos.begin(); it2 != lutIt->second->pos.end(); ++it2) {
            std::cout << **it2 << " ";
          }
          std::cout << "\n";
        }
        std::cout << seq;
#endif
        continue;
      }
      ret = algo.findReverseCycle(it, i);
      if (ret != NO_CYCLE_FOUND) {
        while (!queue.empty()) {
          queue.pop();
        }
        node = lut[FIRST_NODE]->nexts.begin()->second->toNode;
        for (auto it = node->pos.begin(); it != node->pos.end(); ++it) {
          queue.push(*it);
        }
#ifdef VERBOSE
        for (std::map<int, Node*>::iterator lutIt = lut.begin();
             lutIt != lut.end();
             lutIt++) {
          std::cout << *(lutIt->second);
          std::cout << "Pos: ";
          for (auto it2 = lutIt->second->pos.begin(); it2 != lutIt->second->pos.end(); ++it2) {
            std::cout << **it2 << " ";
          }
          std::cout << "\n";
        }
        std::cout << seq;
#endif
        continue;
      }
      if (*++it != LAST_NODE)
        queue.push(it);
    }
  }


  for (std::map<int, Node*>::iterator it = lut.begin();
      it != lut.end();
      it++) {
    std::cout << *(it->second);
    std::cout << "Pos: ";
    for (auto it2 = it->second->pos.begin(); it2 != it->second->pos.end(); ++it2) {
      std::cout << **it2 << " ";
    }
    std::cout << "\n";
  }

  std::cout << seq;


  auto it = seq.begin();
  node = lut[*it];
  auto startBranchIt = it;
  int pathMult = node->nexts[*++it]->multiplicity;
  int currMult;
  for (; it != seq.end();) {
    node = lut[*it];
    if (++it == seq.end()) {
      break;
    }
    currMult = node->nexts[*it]->multiplicity;
    if ((pathMult != currMult) || (*it <= FIRST_NODE)) {
      std::cout << "Multiplicity: " << pathMult << " - ";
      while (startBranchIt != it) {
        std::cout << *startBranchIt++ << " ";
      }
      std::cout << "\n";
      startBranchIt = it;
      if (*it > FIRST_NODE) {
        --startBranchIt;
      }

      pathMult = currMult;
    }
  }

  return 0;
}
